package com.openess.bigsearch.engine.utils;

import java.lang.reflect.Array;
import java.util.Iterator;

/**
 * 基于堆排序实现的优先级队列，最小堆，超过数组界限的将最小值剔除队列
 * 
 * @author TuTu
 * 
 */
public class PriorityQueue<E extends Comparable<E>> implements QQueue<E> {
	/**
	 * 堆的大小，即已建立好最大堆的子树的元素个数。优先队列和堆排序还略有不同，这里的count也代表队列中元素的个数，因为队列中所有的元素都是排好序的，
	 * 每入队一个元素，都会重新保持一次堆性质。
	 */
	private int count;
	/**
	 * 进行排序的数组
	 */
	private E[] array;

	/**
	 * 构造方法，默认指定了一个队列的大小
	 */
	public PriorityQueue() {
		this(20);
	}

	/**
	 * 构造方法
	 * 
	 * @param size
	 *            指定队列的大小
	 */
	public PriorityQueue(int size) {
		array = (E[]) new Comparable[size];
	}

	/**
	 * 左孩子
	 * 
	 * @param i
	 * @return
	 */
	private int left(int i) {
		return 2 * (i + 1) - 1;
	}

	/**
	 * 右孩子
	 * 
	 * @param i
	 * @return
	 */
	private int right(int i) {
		return 2 * (i + 1);
	}

	/**
	 * 拿到父母的位置
	 * 
	 * @param i
	 * @return
	 */
	protected int parent(int i) {
		return (i - 1) / 2;
	}

	/**
	 * 堆的大小，不等于数组的大小
	 * 
	 * @return
	 */
	protected int heapSize() {
		return count;
	}

	/**
	 * 数组中所有元素的个数
	 * 
	 * @param arrays
	 * @return
	 */
	private int length(E[] arrays) {
		return arrays.length;
	}

	/**
	 * 判断队列是否已满
	 * 
	 * @return
	 */
	public boolean isFull() {
		return count == array.length;
	}

	/**
	 * 优先队列中实际的元素个数，不算空位
	 * 
	 * @return
	 */
	public int size() {
		return count;
	}

	/**
	 * 链表的遍历实现，Itr不能加泛型，否则会造成内部类中的E无法与外部类中的E进行匹配，被认为不是一个类型
	 * 
	 * @author TuTu
	 * 
	 */
	private class Itr implements Iterator<E> {
		int i = 0;

		@Override
		public boolean hasNext() {
			return i < count;
		}

		@Override
		public E next() {
			return array[i++];
		}

		@Override
		public void remove() {
		}

	}

	@Override
	public Iterator<E> iterator() {
		return new Itr();
	}

	@Override
	public boolean contain(E elements) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public <T> T[] toArray(T[] a) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public <T> T[] toArray(T a) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Object toArray() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public boolean isEmpty() {
		return count == 0;
	}

	@Override
	public boolean enqueue(E element) {
		if (element == null) {
			return false;
		}
		// 如果队列满了，那么就将最小值剔除掉
		if (isFull()) {
			dequeue();
		}
		heapDecreaseKey(array, element);
		count++;
		return true;
	}

	/**
	 * 以指定的位置作为根，构建子树的最小堆。前提：以i为根的树，其左右孩子树已经是最小堆
	 * 
	 * @param arrays
	 *            准备构建最小堆的数组
	 * @param i
	 *            以数组中第i个元素作为根，构建最小堆
	 */
	private void minHeapify(E[] arrays, int i) {
		int smallest;
		int l = left(i);
		int r = right(i);
		// 如果左孩子节点不在堆内，那右孩子节点无需判断即可知必然不会在堆内
		while (l < heapSize()) {
			if (arrays[l].compareTo(arrays[i]) < 0) {
				smallest = l;
			} else {
				smallest = i;
			}
			if (r < heapSize() && arrays[r].compareTo(arrays[smallest]) < 0) {
				smallest = r;
			}
			if (smallest != i) {
				E temp = arrays[i];
				arrays[i] = arrays[smallest];
				arrays[smallest] = temp;
				l = left(smallest);
				r = right(smallest);
				i = smallest;
			} else {
				l = heapSize();
			}
		}
	}

	/**
	 * 对整个数组，进行循环建堆
	 * 
	 * @param arrays
	 */
	private void buildMinHeap(E[] arrays) {
		this.count = length(arrays);
		// 叶子节点没有孩子，不需要建堆，直接从最后一个内节点开始建堆，一直建到整棵树的根节点，即数组的第一个
		for (int i = length(arrays) / 2 - 1; i >= 0; i--) {
			minHeapify(arrays, i);
		}
	}

	/**
	 * 在数组的heapSize位置插入值，并建立成最小堆。前提：0~heapSize-1的数组内容已经是最小堆，且数组还有空位可以插入新元素。
	 * 此处和算法导论里的实现有区别， 主要是对于E类型无法设置其为最大或最小值。因此此处实现的方法专门针对优先队列，而不是在其他地方使用此方法。
	 * 
	 * @param array
	 * @param element
	 */
	private void heapDecreaseKey(E[] array, E element) {
		if (element == null) {
			return;
		}
		int i = count;
		array[i] = element;
		// 只要i不是整颗树的根节点位置，且A[i]的父母比其小，那么就一直从i往上遍历到根节点位置
		while (i > 0 && array[parent(i)].compareTo(element) > 0) {
			E temp = array[i];
			array[i] = array[parent(i)];
			array[parent(i)] = temp;
			i = parent(i);
		}
	}

	@Override
	public E dequeue() {
		if (isEmpty()) {
			return null;
		}
		E min = array[0];
		array[0] = array[count - 1];
		count--;
		minHeapify(array, 0);
		// 返回最小值
		return min;
	}

	@Override
	public String toString() {
		String str = "Size: " + count + ", {";
		for (int i = 0; i < count - 1; i++) {
			str += array[i] + ",";
		}
		str += array[count - 1] + "}";
		return str;
	}

}
